package com.example.javaproject.datastructure.array;

/**
 * Description:排序方法
 * <br>Author：tian
 * <br>Time: 2019/3/12 15:07
 *
 * @see <a href="https://www.cnblogs.com/ysocean/p/7896269.html">冒泡和选择实现原理</a>
 * @see <a href="https://www.cnblogs.com/WuNaiHuaLuo/p/5397041.html">插入实现原理</a>
 */
public class Sort {

    public static void main(String[] args) {
        int[] array = {4, 2, 8, 9, 5, 7, 6, 1, 3};
        Sort sort = new Sort();
        sort.bubbleSort(array);
//        sort.choiceSort(array);
//        sort.insertDirectlySort(array);
    }

    /**
     * 冒泡排序
     *
     * @param array
     */
    private void bubbleSort(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            boolean flag = true; // 标志位标识有没有进行过交互顺序
            for (int j = 0; j < array.length - 1 - i; j++) {
                if (array[j] > array[j + 1]) {
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                    flag = false;
                }
            }

            if(flag) {
                break;
            }

            System.out.println("第" + i + "轮排序，排序后 ");
            display(array);
        }
    }

    public void display(int[] array) {
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }

        System.out.println();
    }

    /**
     * 选择排序
     *
     * @param array
     */
    public void choiceSort(int[] array) {
        //需要执行N-1轮比较操作
        for (int i = 0; i < array.length - 1; i++) {
            int min = i;
            //每轮需要比较的次数
            for (int j = i + 1; j < array.length; j++) {
                if (array[j] < array[min]) {
                    min = j;//记录能找的最小元素的下班
                }
            }

            if (i != min) {
                int temp = array[min];
                array[min] = array[i];
                array[i] = temp;
            }
            System.out.print("第" + (i + 1) + "轮排序结果：");
            display(array);
        }
    }

    /**
     * 直接插入排序
     *
     * @param array
     */
    public void insertDirectlySort(int[] array) {
        int i;
        int j;
        int temp;  //定义一个临时变量，用于交换数据时存储
        for (i = 1; i < array.length; i++) {  //因为我们要对该待排序列的每一个元素都和前面的已排好序的序列进行插入，所以我们会对序列进行遍历
            for (j = 0; j < i; j++) {  //第二层循环主要用于对已排好序的序列进行扫描，和要插入进来的数据进行逐一比较，然后决定插入到哪里
                if (array[j] > array[i]) {//从前往后对已排好序的元素和待插入元素进行大小比较，然后直到找到一个元素比被插入元素大，则交换位置
                    temp = array[i];
                    array[i] = array[j];
                    array[j] = temp;
                }
            }
        }

        display(array);
    }
}
